// 给定一个可包含重复数字的序列，返回所有不重复的全排列。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */

// 暴露接口
const permuteUnique = function (nums: number[]): number[][] {
    const res: number[][] = []; // 结果数组
    const path: number[] = []; // 路径数组
    nums.sort((a, b) => a - b); // 先对原数组进行排序
    const isSelected: boolean[] = new Array(nums.length).fill(false); // 选择数组
    permuteUnique_DFS(nums, res, path, isSelected);
    return res;
};
// 深度优先遍历+回溯剪枝辅助方法
function permuteUnique_DFS(nums: number[], res: number[][],
    path: number[], isSelected: boolean[]) {
    // 递归出口
    if (path.length === nums.length) {
        res.push(Array.from(path)); // 浅拷贝进一个数组实例
        return;
    }
    // 深度优先遍历--->选择过程
    for (let i = 0; i < nums.length; i++) {
        // 注意这个剪枝条件！
        if (i > 0 && nums[i] === nums[i - 1] && !isSelected[i - 1]) {
            continue;
        }
        if (!isSelected[i]) {
            path.push(nums[i]);
            isSelected[i] = true;
            // 继续深度优先搜索
            permuteUnique_DFS(nums, res, path, isSelected);
            // 回溯过程
            path.pop();
            isSelected[i] = false;
        }
    }
}



permuteUnique(
    [1, 1, 2]);

// 这道题目是一道经典的深度优先遍历 + 回溯算法 + 剪枝的例题
// 首先使用深度优先遍历来解决选择与组合排列的问题
// 因为题目中各个组合可以掉过头来重选，所以显然每一轮次的起点应该从 0 开始
// 但是题目中又规定了每个数字不能在单次组合中多选，所以我们需要设置一个布尔数组
// 用布尔数组来标记表明对应索引的数字是否有被选中
// 这道题目中最复杂的部分在于需要考虑剪枝的条件（题目中给定数组存在相同的数，不剪枝会导致结果重复）
// 我们首先需要对原数组进行排序得到有序
// 然后在每一轮的循环中，如果：
// 当前的元素索引大于0
// 且与前一个元素相等
// 且前一个元素的布尔数组为可选状态
// 说明此时满足的条件是重复的（因为当前元素可以做的选择，前一个元素也能做到，而且已经记录到结果数组里了）
// 这变相表面了当前元素与前一个相同的元素目前正处于相同的路径深度上
// 我们对这种情况做剪枝操作
// 能理清这个部分，这道题目基本上就可以正确的求解出来。
